﻿namespace Leetcode.N0023.V2;

public class Solution
{
    public ListNode MergeKLists(ListNode[] lists)
    {
        var valueLists = new int[lists.Length][];
        var total = 0;
        for (int i = 0; i < valueLists.Length; i++)
        {
            valueLists[i] = this.ConvertTo(lists[i]);
            total += valueLists[i].Length;
        }
        var newValueList = new int[total];
        var count = 0;
        if (valueLists.Length > 0)
        {
            for (int i = 0; i < valueLists[0].Length; i++)
            {
                newValueList[i] = valueLists[0][i];
            }
            count += valueLists[0].Length;
        }

        int from;
        int to = count - 1;
        for (int i = 1; i < valueLists.Length; i++)
        {
            var valueList = valueLists[i];
            from = 0;
            for (int j = 0; j < valueLists[i].Length; j++)
            {
                var pos = this.Find(newValueList, from, to, valueList[j]);
                this.Move(newValueList, pos, to);
                newValueList[pos] = valueList[j];
                from = pos + 1;
                to += 1;
            }
        }

        return this.ConvertFrom(newValueList);
    }

    private int[] ConvertTo(ListNode node)
    {
        var list = new System.Collections.Generic.List<int>();
        var p = node;
        while (p != null)
        {
            list.Add(p.val);
            p = p.next;
        }
        return list.ToArray();
    }

    private ListNode ConvertFrom(int[] value)
    {
        if (value.Length == 0)
        {
            return null;
        }
        var root = new ListNode(value[0]);
        var node = root;
        for (int i = 1; i < value.Length; i++)
        {
            node.next = new ListNode(value[i]);
            node = node.next;
        }
        return root;
    }



    private void Move(int[] node, int from, int to)
    {
        for (int i = to + 1; i > from; i--)
        {

            node[i] = node[i - 1];
        }
    }

    private int Find(int[] node, int from, int to, int value)
    {
        int pos = from;
        var findPos = pos;
        while (from < to)
        {
            var step = (to - from + 1) / 2;

            pos = from + step;
            if (node[pos] <= value)
            {
                from = pos + 1;
            }
            else
            {
                to = pos - 1;
            }
        }
        if (from > to)
        {
            return from;
        }
        return node[from] <= value ? from + 1 : from;
    }

}
